package Lab11;

import java.util.*;

public class BST<E> implements Tree<E> {
    protected TreeNode<E> root;
    protected int size = 0;
    protected java.util.Comparator<E> c;

    /**
     * Create a default BST with a natural order comparator
     */
    public BST() {
        this.c = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);
    }

    /**
     * Create a BST with a specified comparator
     */
    public BST(java.util.Comparator<E> c) {
        this.c = c;
    }

    /**
     * Create a binary tree from an array of objects
     */
    public BST(E[] objects) {
        this.c = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);
        for (int i = 0; i < objects.length; i++)
            add(objects[i]);
    }

    @Override
    /** Returns true if the element is in the tree */
    public boolean search(E e) {
        TreeNode<E> current = root; // Start from the root

        while (current != null) {
            if (c.compare(e, current.element) < 0) {
                current = current.left;
            } else if (c.compare(e, current.element) > 0) {
                current = current.right;
            } else // element matches current.element
                return true; // Element is found
        }

        return false;
    }

    @Override
    /** Insert element e into the binary tree
     * Return true if the element is inserted successfully */
    public boolean insert(E e) {
        if (root == null)
            root = createNewNode(e); // Create a new root
        else {
            // Locate the parent node
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
            while (current != null)
                if (c.compare(e, current.element) < 0) {
                    parent = current;
                    current = current.left;
                } else if (c.compare(e, current.element) > 0) {
                    parent = current;
                    current = current.right;
                } else
                    return false; // Duplicate node not inserted

            // Create the new node and attach it to the parent node
            if (c.compare(e, parent.element) < 0)
                parent.left = createNewNode(e);
            else
                parent.right = createNewNode(e);
        }

        size++;
        return true; // Element inserted successfully
    }

    protected TreeNode<E> createNewNode(E e) {
        return new TreeNode<>(e);
    }

    @Override
    /** Inorder traversal from the root */
    public void inorder() {
        inorder(root);
    }

    /**
     * Inorder traversal from a subtree
     */
    protected void inorder(TreeNode<E> root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.element + " ");
        inorder(root.right);
    }

    @Override
    /** Postorder traversal from the root */
    public void postorder() {
        postorder(root);
    }

    /**
     * Postorder traversal from a subtree
     */
    protected void postorder(TreeNode<E> root) {
        if (root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.element + " ");
    }

    @Override
    /** Preorder traversal from the root */
    public void preorder() {
        preorder(root);
    }

    /**
     * Preorder traversal from a subtree
     */
    protected void preorder(TreeNode<E> root) {
        if (root == null) return;
        System.out.print(root.element + " ");
        preorder(root.left);
        preorder(root.right);
    }

    /**
     * This inner class is static, because it does not access
     * any instance members defined in its outer class
     */
    public static class TreeNode<E> {
        protected E element;
        protected TreeNode<E> left;
        protected TreeNode<E> right;

        public TreeNode(E e) {
            element = e;
        }
    }

    @Override
    /** Get the number of nodes in the tree */
    public int getSize() {
        return size;
    }

    /**
     * Returns the root of the tree
     */
    public TreeNode<E> getRoot() {
        return root;
    }

    /**
     * Returns a path from the root leading to the specified element
     */
    public java.util.ArrayList<TreeNode<E>> path(E e) {
        java.util.ArrayList<TreeNode<E>> list =
                new java.util.ArrayList<>();
        TreeNode<E> current = root; // Start from the root

        while (current != null) {
            list.add(current); // Add the node to the list
            if (c.compare(e, current.element) < 0) {
                current = current.left;
            } else if (c.compare(e, current.element) > 0) {
                current = current.right;
            } else
                break;
        }

        return list; // Return an array list of nodes
    }

    @Override
    /** Delete an element from the binary tree.
     * Return true if the element is deleted successfully
     * Return false if the element is not in the tree */
    public boolean delete(E e) {
        // Locate the node to be deleted and also locate its parent node
        TreeNode<E> parent = null;
        TreeNode<E> current = root;
        while (current != null) {
            if (c.compare(e, current.element) < 0) {
                parent = current;
                current = current.left;
            } else if (c.compare(e, current.element) > 0) {
                parent = current;
                current = current.right;
            } else
                break; // Element is in the tree pointed at by current
        }

        if (current == null)
            return false; // Element is not in the tree

        // Case 1: current has no left child
        if (current.left == null) {
            // Connect the parent with the right child of the current node
            if (parent == null) {
                root = current.right;
            } else {
                if (c.compare(e, parent.element) < 0)
                    parent.left = current.right;
                else
                    parent.right = current.right;
            }
        } else {
            // Case 2: The current node has a left child
            // Locate the rightmost node in the left subtree of
            // the current node and also its parent
            TreeNode<E> parentOfRightMost = current;
            TreeNode<E> rightMost = current.left;

            while (rightMost.right != null) {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right; // Keep going to the right
            }

            // Replace the element in current by the element in rightMost
            current.element = rightMost.element;

            // Eliminate rightmost node
            if (parentOfRightMost.right == rightMost)
                parentOfRightMost.right = rightMost.left;
            else
                // Special case: parentOfRightMost == current
                parentOfRightMost.left = rightMost.left;
        }

        size--; // Reduce the size of the tree
        return true; // Element deleted successfully
    }
//
//    @Override
//    /** Obtain an iterator. Use inorder. */
//    public java.util.Iterator<E> iterator() {
//        return new InorderIterator();
//    }
//
//    // Inner class InorderIterator
//    private class InorderIterator implements java.util.Iterator<E> {
//        // Store the elements in a list
//        private java.util.ArrayList<E> list =
//                new java.util.ArrayList<>();
//        private int current = 0; // Point to the current element in list
//
//        public InorderIterator() {
//            inorder(); // Traverse binary tree and store elements in list
//        }
//
//        /**
//         * Inorder traversal from the root
//         */
//        private void inorder() {
//            inorder(root);
//        }
//
//        /**
//         * Inorder traversal from a subtree
//         */
//        private void inorder(TreeNode<E> root) {
//            if (root == null) return;
//            inorder(root.left);
//            list.add(root.element);
//            inorder(root.right);
//        }
//
//        @Override
//        /** More elements for traversing? */
//        public boolean hasNext() {
//            if (current < list.size())
//                return true;
//
//            return false;
//        }
//
//        @Override
//        /** Get the current element and move to the next */
//        public E next() {
//            return list.get(current++);
//        }
//
//        @Override // Remove the element returned by the last next()
//        public void remove() {
//            if (current == 0) // next() has not been called yet
//                throw new IllegalStateException();
//
//            delete(list.get(--current));
//            list.clear(); // Clear the list
//            inorder(); // Rebuild the list
//        }
//    }

    @Override
    /** Remove all elements from the tree */
    public void clear() {
        root = null;
        size = 0;
    }


    // Q1:
    public void nonRecursiveInorder(){
        Stack<TreeNode<E>> nodes = new Stack<>();
        ArrayList<TreeNode<E>> stack = new ArrayList<>();
        nodes.push(root);
        TreeNode<E> current;
        while(!nodes.isEmpty()){
            current = nodes.peek();
            if(current.left!=null&&!stack.contains(current.left)){
                nodes.push(current.left);
                stack.add(current.left);
            }else{
                System.out.print(nodes.pop().element + " ");
                if(current.right!=null) {
                    nodes.push(current.right);
                    stack.add(current.right);
                }
            }
        }
    }

    // Q2:
    /**
     * Inorder traversal from the root
     */
    public void nonRecursivePreorder() {
        ArrayList<TreeNode<E>> list = new ArrayList<TreeNode<E>>();
        Stack<TreeNode<E>> stack = new Stack<TreeNode<E>>();
        TreeNode<E> node;

        if (root == null) return;

        stack.push(root);

        while (!stack.isEmpty()) {
            System.out.print((node = stack.pop()).element + " "); // Remove the node from the stack

            if (node.right != null && !list.contains(node.right)) {
                stack.push(node.right); // Add the right node to the stack
            }

            if (node.left != null && !list.contains(node.left)) {
                stack.push(node.left); // Add the left node to the stack
            }
        }

    }

    // Q4:
    public Iterator<E> iterator(){ return new preorderIterator();}

    private class preorderIterator implements Iterator<E>{
        private int index = 0;
        private ArrayList<E> list = new ArrayList<>();

        public preorderIterator(){
            preOrder(root);
        }

        private void preOrder(TreeNode<E> node){
            if(node == null) return;
            list.add(node.element);
            preOrder(node.left);
            preOrder(node.right);
        }

        @Override
        public boolean hasNext() {
            return index<list.size();
        }

        @Override
        public E next() {
            return list.get(index++);
        }

        @Override
        public void remove() {
            delete(list.get(index));
            list.clear();
            preOrder(root);
        }
    }


    public static BST typeTree() {
        BST tree = new BST();
        Scanner scan = new Scanner(System.in);
        System.out.print("type 10 integers: ");
        for (int i = 0; i < 10; i++) {
            tree.add(scan.nextInt());
        }
        return tree;
    }


    // test
    public static void main(String[] args){
        BST tree = new BST(new Integer[]{1,2,0,3,-1,4,-2});

        tree.inorder();
        System.out.println();
        tree.nonRecursiveInorder();

        System.out.println("\n");
        tree.preorder();
        System.out.println();
        tree.nonRecursivePreorder();

        LinkedList<Integer>[] test = new LinkedList[3];
        test[2]= new LinkedList<>();
    }

}
